对于每个位置 , 我们向 连一条边。 结合题意可知,一个合法的排列,是一个由 个自环组成的图。
但现在会形成多个环,不妨记环的数量为 , 第 个环的大小为 (包括自环)。
我们现在要做的,就是将这 个环拆成 个自环。
显然,对于一个大小为 的环,拆成自环至少需要 次操作。
记 , 表示将 个点的环 , 拆成 个点的环 + 个点的环的方案数。
显然有
记 表示大小为 的环的拆分方案数() , 则根据多重集的排列公式得:
这样递推的复杂度是 的 ,给一份代码:
f[ 1 ] = 1;
for( int i = 2 ; i <= MAXN ; i ++ ) {
for( int x = 1 ; x <= i / 2 ; x ++ ) {
int y = i - x , t = x == y ? i / 2 : i;
f[ i ] += t * f[ x ] * f[ y ] * ( Fac[ i - 2 ] / Fac[ x - 1 ] / Fac[ y - 1 ] );
}
printf("%d %d\n", i , f[ i ] );
}
经过找规律,我们发现,,现在就可以求出了。
答案也是一个多重集,可以简单求出
#include <cstdio>
#include <cstring>
using namespace std;
#define Mod 1000000009
const int MAXN = 100000;
int t , n , p[ MAXN + 5 ] , s[ MAXN + 5 ] , k;
bool vis[ MAXN + 5 ];
int Quick_pow( int x , int po ) {
int Ans = 1;
while( po ) {
if( po % 2 ) Ans = 1ll * Ans * x % Mod;
x = 1ll * x * x % Mod;
po /= 2;
}
return Ans;
}
int Inv( int x ) {
return Quick_pow( x , Mod - 2 );
}
int dfs( int u ) {
if( vis[ u ] ) return 0;
vis[ u ] = 1;
return dfs( p[ u ] ) + 1;
}
int f[ MAXN + 5 ] , Fac[ MAXN + 5 ] , InvFac[ MAXN + 5 ];
void Init( ) {
f[ 1 ] = 1;
for( int i = 2 ; i <= MAXN ; i ++ )
f[ i ] = Quick_pow( i , i - 2 );
Fac[ 0 ] = 1;
for( int i = 1 ; i <= MAXN ; i ++ )
Fac[ i ] = 1ll * Fac[ i - 1 ] * i % Mod;
InvFac[ MAXN ] = Inv( Fac[ MAXN ] );
for( int i = MAXN - 1 ; i >= 0 ; i -- )
InvFac[ i ] = 1ll * InvFac[ i + 1 ] * ( i + 1 ) % Mod;
}
int main( ) {
Init( );
scanf("%d",&t);
while( t -- ) {
k = 0;
memset( vis , 0 , sizeof( vis ) );
memset( s , 0 , sizeof( s ) );
scanf("%d",&n);
for( int i = 1 ; i <= n ; i ++ )
scanf("%d",&p[ i ]);
for( int i = 1 ; i <= n ; i ++ )
if( !vis[ i ] ) s[ ++ k ] = dfs( i );
int p1 = 1 , p2 = 1 , p3 = Fac[ n - k ];
for( int i = 1 ; i <= k ; i ++ ) {
p1 = 1ll * p1 * f[ s[ i ] ] % Mod;
p2 = 1ll * p2 * Fac[ s[ i ] - 1 ] % Mod;
}
printf("%d\n", 1ll * p1 * Inv( p2 ) % Mod * p3 % Mod );
}
return 0;
}